動的セグメント木 (DynamicSegTree)
自分で改造したやつなので間違ってるかも
参考
概要
各ノードが2つの子ノードを持っていて、子ノードが更新されたら自ノードも更新する
長所
実際に必要となるノード数が十分小さければ、大きなサイズの数列に対するクエリも、先読みや座標圧縮をすることなく処理することができる。
短所
通常のセグ木と比較してメモリアクセスが遅い。
一点取得の時間計算量は、通常のセグ木では Θ(1)であるのに対して、Dynamic Segment Tree では O(log(n))となる。
使用方法
Nodeクラスの中身を編集して使う
DynamicSegTreeはたぶん変えなくていい
DynamicSegTreeのメソッドはACLのSegTreeのset、prod、all_prodと同じように使える
getも追加したほうがいいかも
実装
code: python
class Node:
def __init__(self, l, r):
self.l = l
self.r = r
self.left = None
self.right = None
self.len = 0
self.value = 0
def update(self):
"""子ノードの情報を元に自ノードの情報を更新する"""
left_child: Node = self.left
right_child: Node = self.right
left_len = left_child.len if left_child else 0
right_len = right_child.len if right_child else 0
left_value = left_child.value if left_child else 0
right_value = right_child.value if right_child else 0
self.len = left_len + right_len
self.value = left_value + right_value
def set(self, val):
"""自ノードの値をvalに追加する"""
self.len += 1
self.value += val
class DynamicSegTree:
def __init__(self, size):
self.N = size
self.root = Node(0, self.N)
def set(self, pos, val, node: Node | None=None):
"""posにvalをセットする"""
if node is None:
node = self.root
if node.r - node.l == 1:
node.set(val)
return
mid = (node.l + node.r) // 2
if pos < mid:
if not node.left:
node.left = Node(node.l, mid)
self.set(pos, val, node.left)
else:
if not node.right:
node.right = Node(mid, node.r)
self.set(pos, val, node.right)
node.update()
def prod(self, left, right, node: Node | None=None):
"""[left, right)の区間の和を求める"""
if node is None:
node = self.root
if node.r <= left or right <= node.l:
return 0
if left <= node.l and node.r <= right:
return node.value
left_sum = self.prod(left, right, node.left) if node.left else 0
right_sum = self.prod(left, right, node.right) if node.right else 0
return left_sum + right_sum
def all_prod(self):
return self.root.value
使用例
code: text
すベて 0で初期化された長さ nの数列 A=(a_0,a_1,…,a_n-1)があります。
以下で説明されるクエリを q回、オンラインで処理してください。クエリは 2 種類あります。
クエリ 1：p,xが与えられるので、a_pに xを加算する。
クエリ 2：l,rが与えられるので、∑r-1,i=l a_iを報告する。
ただし 1≤n≤10^9,1≤q≤10^5である。
code: python
q = int(input())
N = 10 ** 9
dst = DynamicSegTree(N + 1)
for _ in range(q):
query = list(map(int, input().split()))
dst.set(p, x)
else:
print(dst.prod(l, r))